package linked_list

import (
	"fmt"
	"go-demo/utils"
)

type DoublyNode struct {
	data Elem
	prev *DoublyNode
	next *DoublyNode
}

// 创建一个节点
func NewDoublyNode(data Elem) *DoublyNode {
	return &DoublyNode{
		data: data,
	}
}

// 当前节点的前一个节点
func (n *DoublyNode) ToString() {
	fmt.Print(fmt.Sprintf("%v\t",n.data))
}

// 当前节点的前一个节点
func (n *DoublyNode) Prev() (prev *DoublyNode) {
	return n.prev
}

// 当前节点的前一个节点
func (n *DoublyNode) Next() (next *DoublyNode) {
	return n.next
}

// 获取节点的值
func (n *DoublyNode) GetValue() Elem {
	return utils.If(n == nil, nil, n.data)
}

type DoublyLinkedList struct {
	head *DoublyNode // 表头节点
	tail *DoublyNode // 表尾节点
	size int         // 链表的长度
}

// 当前节点的前一个节点
func (l *DoublyLinkedList) String(){
	head := l.head
	for i:=0;i<l.size;i++ {
		fmt.Printf("\t%v",head.data)
		head = head.next
	}
	fmt.Println()
}

// 创建一个空链表
func NewDoublyLinkedList() *DoublyLinkedList {
	return &DoublyLinkedList{}
}

// 返回链表头节点
func (l *DoublyLinkedList) Head() *DoublyNode {
	return l.head
}

// 返回链表尾节点
func (l *DoublyLinkedList) Tail() *DoublyNode {
	return l.tail

}

// 返回链表长度
func (l *DoublyLinkedList) Len() int {
	return l.size

}

// 在链表的右边插入一个元素
func (l *DoublyLinkedList) RPush(data Elem) {
	node := NewDoublyNode(data)
	// 链表未空的时候
	if l.Len() == 0 {
		l.head = node
		l.tail = node
	} else {
		tail := l.tail
		tail.next = node
		node.prev = tail

		l.tail = node
	}
	l.size++
	return
}

// 从链表左边取出一个节点
func (l *DoublyLinkedList) LPop() (node *DoublyNode) {
	// 数据为空
	if l.Len() == 0 {
		return
	}
	node = l.head
	if node.next == nil {
		// 链表为空
		l.head = nil
		l.tail = nil
	} else {
		l.head = node.next
	}
	l.size--
	return
}

// 通过索引查找节点
// 查不到节点则返回空
func (l *DoublyLinkedList) Index(index int) (node *DoublyNode) {
	// 索引为负数则表尾开始查找
	if index < 0 {
		index = (-index) - 1
		node = l.tail
		for {
			// 未找到
			if node == nil {
				return
			}
			// 查到数据
			if index == 0 {
				return
			}

			node = node.prev
			index--
		}
	} else {
		node = l.head
		for ; index > 0 && node != nil; index-- {
			node = node.next
		}
	}

	return
}

// 返回指定区间的元素
func (l *DoublyLinkedList) Range(start, end int) (nodes []*DoublyNode) {
	nodes = make([]*DoublyNode, 0)

	// 转为自然数
	if start < 0 {
		start = l.size + start
		if start < 0 {
			start = 0
		}
	}

	if end < 0 {
		end = l.size + end
		if end < 0 {
			end = 0
		}
	}

	// 区间个数
	rangeLen := end - start + 1
	if rangeLen < 0 {
		return
	}

	startNode := l.Index(start)
	for i := 0; i < rangeLen; i++ {
		if startNode == nil {
			break
		}
		nodes = append(nodes, startNode)
		startNode = startNode.next
	}

	return
}
